package com.company.algo.niuke;

import com.company.algo.pojo.ListNode;

import java.util.Stack;

/**【不会的】
 给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
 输出：2 -> 1 -> 9，即912
 反向存放：
 从两个链表头开始相加，处理进位（单位之和大于10的问题）。创建新的链表节点。然后连接节点
 正向存放：
 利用栈先进后出，计算每一位的和，累加过程处理与反向一致。每一步处理连接节点摆放位置不同。
 */
public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        int carry = 0, sum = 0;
        //当carr!=0时说明有进位存在，即便l1和l2以及遍历完也需要额外添加一个新的节点
        while (l1!=null || l2!= null || carry!=0){
            sum = 0;
            if (l1 != null){
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null){
                sum += l2.val;
                l2 = l2.next;
            }
            sum += carry;
            carry = sum/10;
            cur.next = new ListNode(sum%10);
            cur = cur.next;
        }
        return head.next;
    }

    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1!=null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2!=null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode head = new ListNode(-1);
        int carry = 0, sum;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry!=0){
            sum = carry;
            if (!stack1.isEmpty()) sum += stack1.pop();
            if (!stack2.isEmpty()) sum += stack2.pop();
            carry = sum/10;
            //todo 头插法
            ListNode cur =  new ListNode(sum %10);
            cur.next = head.next;
            head.next = cur;
        }
        return head.next;
    }

    public static void main(String[] args) {
        AddTwoNumbers Main = new AddTwoNumbers();
        ListNode l1 = new ListNode(7);
        l1.next = new ListNode(1);
        l1.next.next = new ListNode(6);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(9);
        l2.next.next = new ListNode(3);
        ListNode head = Main.addTwoNumbers2(l1, l2);
        while (head!=null){
            System.out.print(head.val+"->");
            head = head.next;
        }
    }
}
